package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         146,
		Discription: "LRU",
		Level:       2,
		Labels: map[string]int{
			"双向链表": 1,
			"链表":   1,
			"哈希表":  1,
			"虚拟指针": 1,
		},
	})
}

// LRUCache
//为什么是链表：删除、插入操作频繁
//为什么是双向链表：删除的时候需要将前后两个节点相连，为了快速定位到前一个节点
//为什么需要哈希表：根据key快速定位到对应的指针，也就是在链表中对应的位置，方便移动指针
//为什么需要虚拟头指针和尾指针：方便快速定位到头尾元素，以及在头尾进行删插
type LRUCache struct {
	nodeMap  map[int]*TowSideNode
	preHead  *TowSideNode
	postTail *TowSideNode
	curSize  int
	capacity int
}

type TowSideNode struct {
	Key  int
	Val  int
	Pre  *TowSideNode
	Next *TowSideNode
}

func Constructor(capacity int) LRUCache {
	head := &TowSideNode{}
	tail := &TowSideNode{}
	head.Next = tail
	tail.Pre = head
	return LRUCache{
		nodeMap:  make(map[int]*TowSideNode, 0),
		preHead:  head,
		postTail: tail,
		curSize:  0,
		capacity: capacity,
	}
}

func (cache *LRUCache) Get(key int) int {
	node, exist := cache.nodeMap[key]
	if !exist {
		return -1
	}

	val := node.Val
	cache.deleteNode(node)
	cache.addNodeToHead(node)
	return val
}

func (cache *LRUCache) Put(key int, value int) {
	existNode, exist := cache.nodeMap[key]
	if exist {
		existNode.Val = value
		cache.deleteNode(existNode)
		cache.addNodeToHead(existNode)
		return
	}

	node := &TowSideNode{
		Key: key,
		Val: value,
	}
	cache.addNodeToHead(node)
}

func (cache *LRUCache) deleteNode(node *TowSideNode) {
	pre := node.Pre
	next := node.Next
	pre.Next = next
	next.Pre = pre
	cache.curSize--
	delete(cache.nodeMap, node.Key)
}

func (cache *LRUCache) addNodeToHead(node *TowSideNode) {
	curHead := cache.preHead.Next
	cache.preHead.Next = node
	node.Pre = cache.preHead
	node.Next = curHead
	curHead.Pre = node
	cache.curSize++
	cache.nodeMap[node.Key] = node

	if cache.curSize > cache.capacity {
		cache.deleteNode(cache.postTail.Pre)
	}
}
